package leetcode_core.leetcode_1;

public class Solve {
    public void solve(char[][] board) {
        if(board.length == 0){
            return;
        }
        int m = board.length;//行数
        int n = board[0].length;//列数
        UnionFind UF = new UnionFind(m*n+1);
        int dummy = m*n;
        //将首列的O与末列的O连通
        for(int i = 0;i<m;i++){
            if(board[i][0] == 'O'){
                UF.union(i*n,dummy);
            }
            if(board[i][n-1] == 'O'){
                UF.union(i*n+n-1,dummy);
            }
        }
        //将首行和末行的O连通
        for(int j = 0;j<n;j++){
            if(board[0][j] == 'O'){
                UF.union(j,dummy);
            }
            if(board[m-1][j] == 'O'){
                UF.union((m-1)*n+j,dummy);
            }
        }
        int[][] steps = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        for (int i = 1;i<m-1;i++){
            for(int j =1;j<n-1;j++){
                if(board[i][j] == 'O'){
                    //将此O与上下左右的O给连通
                    for(int k =0;k<4;k++){
                        int x = i + steps[k][0];
                        int y = i + steps[k][1];
                        if (board[x][y] == 'O'){
                            UF.union(x*n+y,i*n+j);
                        }
                    }
                }
            }
        }
        for(int i = 1;i<m-1;i++){
            for(int j = 1;j<n-1;j++){
                if(!UF.isConnected(dummy,i*n+j)){
                    board[i][j] = 'X';
                }
            }
        }
    }
    class UnionFind {
        //记录连通分量
        private int count;
        //数组定义:节点x的父亲节点是parent[x]
        private int[] parent;
        //新增一个数组记录树的重量
        private int[] size;

        public UnionFind(int n){
            //一开始各自不连通,那么就各自指向自己
            this.count = n;
            parent = new int[n];
            for(int i = 0;i<n;i++){
                parent[i] = i;
                size[i] = 1;//树的尺寸一开始都是1
            }
        }

        //将p节点和q节点进行链接
        public void union(int p,int q){
            int rootP = find(p);
            int rootQ = find(q);
            if(rootP == rootQ){
                return ;
            }
            //小树接到大树下面,比较平衡
            if(size[rootP] > size[rootQ]){
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            }else{
                parent[rootP] += rootQ;
                size[rootQ] += rootP;
            }
            this.count -- ;
        }
        //判断p和q是否连同
        public boolean isConnected(int p,int q){
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }
        //返回图中有几个连通分量
        public int count(){
            return count;
        }

        private int find(int x){//寻找根节点
            //根节点的parent[x] == x
            //这段代码的逻辑:x=parent[x],x赋值为其父节点的值
            //也就是向根节点逼近
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
    }
}


